package org.example.Greedy_Algorithm;

import java.util.Arrays;
import java.util.Comparator;

public class Nonoverlapping_interval {
    public static void main(String[] args) {
        //无重叠区间

        //给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。
        int[][] intervals = {{1,100},{11,22},{1,11},{2,12}};
        int i = eraseOverlapIntervals(intervals);
        System.out.println(i);
    }
    public static int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] a, int[] b) {
                return Integer.compare(a[0],b[0]);
            }
        });
        System.out.println(Arrays.deepToString(intervals));
        int num = 0;
        for (int i = 0; i < intervals.length-1; i++) {
            if (intervals[i+1][0]<intervals[i][1]){
                intervals[i+1][1] = Math.min(intervals[i][1],intervals[i+1][1]);
                num++;
            }
        }
        return num;
    }
}
